home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 8: LINUX Games / Linux Cubed Series 8 - LINUX Games.iso / games / muds / lpmud312.tar / lpmud312 / regexp.c < prev    next >
C/C++ Source or Header  |  1991-12-10  |  34KB  |  1,420 lines
  1. /* 
  2.  *
  3.  * regexp.c - regular expression matching
  4.  *
  5.  * DESCRIPTION
  6.  *
  7.  *    Underneath the reformatting and comment blocks which were added to 
  8.  *    make it consistent with the rest of the code, you will find a
  9.  *    modified version of Henry Specer's regular expression library.
  10.  *    Henry's functions were modified to provide the minimal regular
  11.  *    expression matching, as required by P1003.  Henry's code was
  12.  *    copyrighted, and copy of the copyright message and restrictions
  13.  *    are provided, verbatim, below:
  14.  *
  15.  *    Copyright (c) 1986 by University of Toronto.
  16.  *    Written by Henry Spencer.  Not derived from licensed software.
  17.  *
  18.  *    Permission is granted to anyone to use this software for any
  19.  *    purpose on any computer system, and to redistribute it freely,
  20.  *    subject to the following restrictions:
  21.  *
  22.  *    1. The author is not responsible for the consequences of use of
  23.  *         this software, no matter how awful, even if they arise
  24.  *       from defects in it.
  25.  *
  26.  *    2. The origin of this software must not be misrepresented, either
  27.  *       by explicit claim or by omission.
  28.  *
  29.  *    3. Altered versions must be plainly marked as such, and must not
  30.  *       be misrepresented as being the original software.
  31.  *
  32.  *
  33.  * This version modified by Ian Phillipps to return pointer to terminating
  34.  * NUL on substitution string. [ Temp mail address ex-igp@camcon.co.uk ]
  35.  *
  36.  *    Altered by amylaar to support excompatible option and the
  37.  *      operators \< and >\ . ( 7.Sep. 1991 )
  38.  *
  39.  * regsub altered by amylaar to take an additional parameter specifying
  40.  * maximum number of bytes that can be written to the memory region
  41.  * pointed to by dest
  42.  *
  43.  *     Beware that some of this code is subtly aware of the way operator
  44.  *     precedence is structured in regular expressions.  Serious changes in
  45.  *     regular-expression syntax might require a total rethink.
  46.  *
  47.  * AUTHORS
  48.  *
  49.  *     Mark H. Colburn, NAPS International (mark@jhereg.mn.org)
  50.  *     Henry Spencer, University of Torronto (henry@utzoo.edu)
  51.  *
  52.  * Sponsored by The USENIX Association for public distribution. 
  53.  *
  54.  */
  55.  
  56. /* Headers */
  57.  
  58. #include <stdio.h>
  59. #include <string.h>
  60. #include <ctype.h>
  61. #include "regexp.h"
  62. #include "lint.h" /* for free() */
  63.  
  64. /*
  65.  * The "internal use only" fields in regexp.h are present to pass info from
  66.  * compile to execute that permits the execute phase to run lots faster on
  67.  * simple cases.  They are:
  68.  *
  69.  * regstart    char that must begin a match; '\0' if none obvious
  70.  * reganch    is the match anchored (at beginning-of-line only)?
  71.  * regmust    string (pointer into program) that match must include, or NULL
  72.  * regmlen    length of regmust string
  73.  *
  74.  * Regstart and reganch permit very fast decisions on suitable starting points
  75.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  76.  * of lines that cannot possibly match.  The regmust tests are costly enough
  77.  * that regcomp() supplies a regmust only if the r.e. contains something
  78.  * potentially expensive (at present, the only such thing detected is * or +
  79.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  80.  * supplied because the test in regexec() needs it and regcomp() is computing
  81.  * it anyway.
  82.  */
  83.  
  84. /*
  85.  * Structure for regexp "program".  This is essentially a linear encoding
  86.  * of a nondeterministic finite-state machine (aka syntax charts or
  87.  * "railroad normal form" in parsing technology).  Each node is an opcode
  88.  * plus a "nxt" pointer, possibly plus an operand.  "Nxt" pointers of
  89.  * all nodes except BRANCH implement concatenation; a "nxt" pointer with
  90.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  91.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  92.  * opposed to a collection of them) is never concatenated with anything
  93.  * because of operator precedence.)  The operand of some types of node is
  94.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  95.  * particular, the operand of a BRANCH node is the first node of the branch.
  96.  * (NB this is *not* a tree structure:  the tail of the branch connects
  97.  * to the thing following the set of BRANCHes.)  The opcodes are:
  98.  */
  99.  
  100. /* definition    number    opnd?    meaning */
  101. #define    END    0        /* no    End of program. */
  102. #define    BOL    1        /* no    Match "" at beginning of line. */
  103. #define    EOL    2        /* no    Match "" at end of line. */
  104. #define    ANY    3        /* no    Match any one character. */
  105. #define    ANYOF    4        /* str    Match any character in this string. */
  106. #define    ANYBUT    5        /* str    Match any character not in this
  107.                  * string. */
  108. #define    BRANCH    6        /* node    Match this alternative, or the
  109.                  * nxt... */
  110. #define    BACK    7        /* no    Match "", "nxt" ptr points backward. */
  111. #define    EXACTLY    8        /* str    Match this string. */
  112. #define    NOTHING    9        /* no    Match empty string. */
  113. #define    STAR    10        /* node    Match this (simple) thing 0 or more
  114.                  * times. */
  115. #define WORDSTART 11        /* node matching a start of a word          */
  116. #define WORDEND 12        /* node matching an end of a word           */
  117. #define    OPEN    20        /* no    Mark this point in input as start of
  118.                  * #n. */
  119.  /* OPEN+1 is number 1, etc. */
  120. #define    CLOSE    30        /* no    Analogous to OPEN. */
  121.  
  122. /*
  123.  * Opcode notes:
  124.  *
  125.  * BRANCH    The set of branches constituting a single choice are hooked
  126.  *        together with their "nxt" pointers, since precedence prevents
  127.  *        anything being concatenated to any individual branch.  The
  128.  *        "nxt" pointer of the last BRANCH in a choice points to the
  129.  *        thing following the whole choice.  This is also where the
  130.  *        final "nxt" pointer of each individual branch points; each
  131.  *        branch starts with the operand node of a BRANCH node.
  132.  *
  133.  * BACK        Normal "nxt" pointers all implicitly point forward; BACK
  134.  *        exists to make loop structures possible.
  135.  *
  136.  * STAR        complex '*', are implemented as circular BRANCH structures 
  137.  *        using BACK.  Simple cases (one character per match) are 
  138.  *        implemented with STAR for speed and to minimize recursive 
  139.  *        plunges.
  140.  *
  141.  * OPEN,CLOSE    ...are numbered at compile time.
  142.  */
  143.  
  144. /*
  145.  * A node is one char of opcode followed by two chars of "nxt" pointer.
  146.  * "Nxt" pointers are stored as two 8-bit pieces, high order first.  The
  147.  * value is a positive offset from the opcode of the node containing it.
  148.  * An operand, if any, simply follows the node.  (Note that much of the
  149.  * code generation knows about this implicit relationship.)
  150.  *
  151.  * Using two bytes for the "nxt" pointer is vast overkill for most things,
  152.  * but allows patterns to get big without disasters.
  153.  */
  154. #define    OP(p)    (*(p))
  155. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  156. #define    OPERAND(p)    ((p) + 3)
  157.  
  158. /*
  159.  * Utility definitions.
  160.  */
  161.  
  162. #define SPECIAL 0x100
  163. #define LBRAC    ('('|SPECIAL)
  164. #define RBRAC    (')'|SPECIAL)
  165. #define ASTERIX    ('*'|SPECIAL)
  166. #define OR_OP    ('|'|SPECIAL)
  167. #define DOLLAR    ('$'|SPECIAL)
  168. #define DOT    ('.'|SPECIAL)
  169. #define CARET    ('^'|SPECIAL)
  170. #define LSQBRAC ('['|SPECIAL)
  171. #define RSQBRAC (']'|SPECIAL)
  172. #define LSHBRAC ('<'|SPECIAL)
  173. #define RSHBRAC ('>'|SPECIAL)
  174. #define    FAIL(m)    { regerror(m); return(NULL); }
  175. #define    ISMULT(c)    ((c) == ASTERIX)
  176. #define    META    "^$.[()|*\\"
  177. #ifndef CHARBITS
  178. #define CHARBITS    0xff
  179. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  180. #else
  181. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  182. #endif
  183. #define ISWORDPART(c) ( isalnum(c) || (c) == '_' )
  184.  
  185. /*
  186.  * Flags to be passed up and down.
  187.  */
  188. #define    HASWIDTH    01    /* Known never to match null string. */
  189. #define    SIMPLE        02    /* Simple enough to be STAR operand. */
  190. #define    SPSTART        04    /* Starts with * */
  191. #define    WORST        0    /* Worst case. */
  192.  
  193. /*
  194.  * Global work variables for regcomp().
  195.  */
  196. static short   *regparse;    /* Input-scan pointer. */
  197. static int      regnpar;    /* () count. */
  198. static char     regdummy;
  199. static char    *regcode;    /* Code-emit pointer; ®dummy = don't. */
  200. static long     regsize;    /* Code size. */
  201.  
  202. /*
  203.  * Forward declarations for regcomp()'s friends.
  204.  */
  205. #ifndef STATIC
  206. #define    STATIC    static
  207. #endif
  208. STATIC char    *reg();
  209. STATIC char    *regbranch();
  210. STATIC char    *regpiece();
  211. STATIC char    *regatom();
  212. STATIC char    *regnode();
  213. STATIC char    *regnext();
  214. STATIC void     regc();
  215. STATIC void     reginsert();
  216. STATIC void     regtail();
  217. STATIC void     regoptail();
  218. #ifdef STRCSPN
  219. STATIC int      strcspn();
  220. #endif
  221.  
  222. /*
  223.  - regcomp - compile a regular expression into internal code
  224.  *
  225.  * We can't allocate space until we know how big the compiled form will be,
  226.  * but we can't compile it (and thus know how big it is) until we've got a
  227.  * place to put the code.  So we cheat:  we compile it twice, once with code
  228.  * generation turned off and size counting turned on, and once "for real".
  229.  * This also means that we don't allocate space until we are sure that the
  230.  * thing really will compile successfully, and we never have to move the
  231.  * code and thus invalidate pointers into it.  (Note that it has to be in
  232.  * one piece because free() must be able to free it all.)
  233.  *
  234.  * Beware that the optimization-preparation code in here knows about some
  235.  * of the structure of the compiled regexp.
  236.  */
  237. regexp *regcomp(exp,excompat)
  238. char           *exp;
  239. int        excompat;    /* \( \) operators like in unix ex */
  240. {
  241.     register regexp *r;
  242.     register char  *scan;
  243.     register char  *longest;
  244.     register int    len;
  245.     int             flags;
  246.     short       *exp2,*dest,c;
  247.     extern char    *xalloc();
  248.  
  249.     if (exp == (char *)NULL)
  250.     FAIL("NULL argument");
  251.  
  252.     exp2=(short*)xalloc( (strlen(exp)+1) * (sizeof(short[8])/sizeof(char[8])) );
  253.     for ( scan=exp,dest=exp2; c= *scan++; ) {
  254.     switch (c) {
  255.         case '(':
  256.         case ')':
  257.         *dest++ = excompat ? c : c | SPECIAL;
  258.         break;
  259.         case '.':
  260.         case '*':
  261.         case '|':
  262.         case '$':
  263.         case '^':
  264.         case '[':
  265.         case ']':
  266.         *dest++ =  c | SPECIAL;
  267.         break;
  268.         case '\\':
  269.         switch ( c = *scan++ ) {
  270.             case '(':
  271.             case ')':
  272.             *dest++ = excompat ? c | SPECIAL : c;
  273.             break;
  274.             case '<':
  275.             case '>':
  276.             *dest++ = c | SPECIAL;
  277.             break;
  278.             case '{':
  279.             case '}':
  280.             FAIL("sorry, unimplemented operator");
  281.             case 'b': *dest++ = '\b'; break;
  282.             case 't': *dest++ = '\t'; break;
  283.             case 'r': *dest++ = '\r'; break;
  284.             default:
  285.             *dest++ = c;
  286.         }
  287.         break;
  288.         default:
  289.         *dest++ = c;
  290.     }
  291.     }
  292.     *dest=0;
  293.     /* First pass: determine size, legality. */
  294.     regparse = exp2;
  295.     regnpar = 1;
  296.     regsize = 0L;
  297.     regcode = ®dummy;
  298.     regc(MAGIC);
  299.     if (reg(0, &flags) == (char *)NULL)
  300.     return ((regexp *)NULL);
  301.  
  302.     /* Small enough for pointer-storage convention? */
  303.     if (regsize >= 32767L)    /* Probably could be 65535L. */
  304.     FAIL("regexp too big");
  305.  
  306.     /* Allocate space. */
  307.     r = (regexp *) xalloc(sizeof(regexp) + (unsigned) regsize);
  308.     if (r == (regexp *) NULL)
  309.     FAIL("out of space");
  310.  
  311.     /* Second pass: emit code. */
  312.     regparse = exp2;
  313.     regnpar = 1;
  314.     regcode = r->program;
  315.     regc(MAGIC);
  316.     if (reg(0, &flags) == NULL)
  317.     return ((regexp *) NULL);
  318.  
  319.     /* Dig out information for optimizations. */
  320.     r->regstart = '\0';        /* Worst-case defaults. */
  321.     r->reganch = 0;
  322.     r->regmust = NULL;
  323.     r->regmlen = 0;
  324.     scan = r->program + 1;    /* First BRANCH. */
  325.     if (OP(regnext(scan)) == END) {    /* Only one top-level choice. */
  326.     scan = OPERAND(scan);
  327.  
  328.     /* Starting-point info. */
  329.     if (OP(scan) == EXACTLY)
  330.         r->regstart = *OPERAND(scan);
  331.     else if (OP(scan) == BOL)
  332.         r->reganch++;
  333.  
  334.     /*
  335.      * If there's something expensive in the r.e., find the longest
  336.      * literal string that must appear and make it the regmust.  Resolve
  337.      * ties in favor of later strings, since the regstart check works
  338.      * with the beginning of the r.e. and avoiding duplication
  339.      * strengthens checking.  Not a strong reason, but sufficient in the
  340.      * absence of others. 
  341.      */
  342.     if (flags & SPSTART) {
  343.         longest = NULL;
  344.         len = 0;
  345.         for (; scan != NULL; scan = regnext(scan))
  346.         if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  347.             longest = OPERAND(scan);
  348.             len = strlen(OPERAND(scan));
  349.         }
  350.         r->regmust = longest;
  351.         r->regmlen = len;
  352.     }
  353.     }
  354.     free((char*)exp2);
  355.     return (r);
  356. }
  357.  
  358. /*
  359.  - reg - regular expression, i.e. main body or parenthesized thing
  360.  *
  361.  * Caller must absorb opening parenthesis.
  362.  *
  363.  * Combining parenthesis handling with the base level of regular expression
  364.  * is a trifle forced, but the need to tie the tails of the branches to what
  365.  * follows makes it hard to avoid.
  366.  */
  367. static char *reg(paren, flagp)
  368. int             paren;        /* Parenthesized? */
  369. int            *flagp;
  370. {
  371.     register char  *ret;
  372.     register char  *br;
  373.     register char  *ender;
  374.     register int    parno;
  375.     int             flags;
  376.  
  377.     *flagp = HASWIDTH;        /* Tentatively. */
  378.  
  379.     /* Make an OPEN node, if parenthesized. */
  380.     if (paren) {
  381.     if (regnpar >= NSUBEXP)
  382.         FAIL("too many ()");
  383.     parno = regnpar;
  384.     regnpar++;
  385.     ret = regnode(OPEN + parno);
  386.     } else
  387.     ret = (char *)NULL;
  388.  
  389.     /* Pick up the branches, linking them together. */
  390.     br = regbranch(&flags);
  391.     if (br == (char *)NULL)
  392.     return ((char *)NULL);
  393.     if (ret != (char *)NULL)
  394.     regtail(ret, br);    /* OPEN -> first. */
  395.     else
  396.     ret = br;
  397.     if (!(flags & HASWIDTH))
  398.     *flagp &= ~HASWIDTH;
  399.     *flagp |= flags & SPSTART;
  400.     while (*regparse == OR_OP) {
  401.     regparse++;
  402.     br = regbranch(&flags);
  403.     if (br == (char *)NULL)
  404.         return ((char *)NULL);
  405.     regtail(ret, br);    /* BRANCH -> BRANCH. */
  406.     if (!(flags & HASWIDTH))
  407.         *flagp &= ~HASWIDTH;
  408.     *flagp |= flags & SPSTART;
  409.     }
  410.  
  411.     /* Make a closing node, and hook it on the end. */
  412.     ender = regnode((paren) ? CLOSE + parno : END);
  413.     regtail(ret, ender);
  414.  
  415.     /* Hook the tails of the branches to the closing node. */
  416.     for (br = ret; br != (char *)NULL; br = regnext(br))
  417.     regoptail(br, ender);
  418.  
  419.     /* Check for proper termination. */
  420.     if (paren && *regparse++ != RBRAC) {
  421.     FAIL("unmatched ()");
  422.     } else if (!paren && *regparse != '\0') {
  423.     if (*regparse == RBRAC) {
  424.         FAIL("unmatched ()");
  425.     } else
  426.         FAIL("junk on end");/* "Can't happen". */
  427.     /* NOTREACHED */
  428.     }
  429.     return (ret);
  430. }
  431.  
  432. /*
  433.  - regbranch - one alternative of an | operator
  434.  *
  435.  * Implements the concatenation operator.
  436.  */
  437. static char  *regbranch(flagp)
  438. int            *flagp;
  439. {
  440.     register char  *ret;
  441.     register char  *chain;
  442.     register char  *latest;
  443.     int             flags;
  444.  
  445.     *flagp = WORST;        /* Tentatively. */
  446.  
  447.     ret = regnode(BRANCH);
  448.     chain = (char *)NULL;
  449.     while (*regparse != '\0' && *regparse != OR_OP && *regparse != RBRAC) {
  450.     latest = regpiece(&flags);
  451.     if (latest == (char *)NULL)
  452.         return ((char *)NULL);
  453.     *flagp |= flags & HASWIDTH;
  454.     if (chain == (char *)NULL)    /* First piece. */
  455.         *flagp |= flags & SPSTART;
  456.     else
  457.         regtail(chain, latest);
  458.     chain = latest;
  459.     }
  460.     if (chain == (char *)NULL)        /* Loop ran zero times. */
  461.     regnode(NOTHING);
  462.  
  463.     return (ret);
  464. }
  465.  
  466. /*
  467.  - regpiece - something followed by possible [*]
  468.  *
  469.  * Note that the branching code sequence used for * is somewhat optimized:  
  470.  * they use the same NOTHING node as both the endmarker for their branch 
  471.  * list and the body of the last branch.  It might seem that this node could 
  472.  * be dispensed with entirely, but the endmarker role is not redundant.
  473.  */
  474. static char *regpiece(flagp)
  475. int            *flagp;
  476. {
  477.     register char  *ret;
  478.     register short  op;
  479.     /* register char  *nxt; */
  480.     int             flags;
  481.  
  482.     ret = regatom(&flags);
  483.     if (ret == (char *)NULL)
  484.     return ((char *)NULL);
  485.  
  486.     op = *regparse;
  487.     if (!ISMULT(op)) {
  488.     *flagp = flags;
  489.     return (ret);
  490.     }
  491.     if (!(flags & HASWIDTH))
  492.     FAIL("* operand could be empty");
  493.     *flagp = (WORST | SPSTART);
  494.  
  495.     if (op == ASTERIX && (flags & SIMPLE))
  496.     reginsert(STAR, ret);
  497.     else if (op == ASTERIX) {
  498.     /* Emit x* as (x&|), where & means "self". */
  499.     reginsert(BRANCH, ret);    /* Either x */
  500.     regoptail(ret, regnode(BACK));    /* and loop */
  501.     regoptail(ret, ret);    /* back */
  502.     regtail(ret, regnode(BRANCH));    /* or */
  503.     regtail(ret, regnode(NOTHING));    /* null. */
  504.     } 
  505.     regparse++;
  506.     if (ISMULT(*regparse))
  507.     FAIL("nested *");
  508.  
  509.     return (ret);
  510. }
  511.  
  512. /*
  513.  - regatom - the lowest level
  514.  *
  515.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  516.  * it can turn them into a single node, which is smaller to store and
  517.  * faster to run.
  518.  */
  519. static char *regatom(flagp)
  520. int            *flagp;
  521. {
  522.     register char  *ret;
  523.     int             flags;
  524.  
  525.     *flagp = WORST;        /* Tentatively. */
  526.  
  527.     switch (*regparse++) {
  528.     case CARET:
  529.     ret = regnode(BOL);
  530.     break;
  531.     case DOLLAR:
  532.     ret = regnode(EOL);
  533.     break;
  534.     case DOT:
  535.     ret = regnode(ANY);
  536.     *flagp |= HASWIDTH | SIMPLE;
  537.     break;
  538.     case LSHBRAC:
  539.     ret = regnode(WORDSTART);
  540.     break;
  541.     case RSHBRAC:
  542.     ret = regnode(WORDEND);
  543.     break;
  544.     case LSQBRAC:{
  545.         register int    class;
  546.         register int    classend;
  547.  
  548.         if (*regparse == CARET) {    /* Complement of range. */
  549.         ret = regnode(ANYBUT);
  550.         regparse++;
  551.         } else
  552.         ret = regnode(ANYOF);
  553.         if (*regparse == RSQBRAC || *regparse == '-')
  554.         regc(*regparse++);
  555.         while (*regparse != '\0' && *regparse != RSQBRAC) {
  556.         if (*regparse == '-') {
  557.             regparse++;
  558.             if (*regparse == RSQBRAC || *regparse == '\0')
  559.             regc('-');
  560.             else {
  561.             class = (CHARBITS & *(regparse - 2)) + 1;
  562.             classend = (CHARBITS & *(regparse));
  563.             if (class > classend + 1)
  564.                 FAIL("invalid [] range");
  565.             for (; class <= classend; class++)
  566.                 regc(class);
  567.             regparse++;
  568.             }
  569.         } else
  570.             regc(*regparse++);
  571.         }
  572.         regc('\0');
  573.         if (*regparse != RSQBRAC)
  574.         FAIL("unmatched []");
  575.         regparse++;
  576.         *flagp |= HASWIDTH | SIMPLE;
  577.     }
  578.     break;
  579.     case LBRAC:
  580.     ret = reg(1, &flags);
  581.     if (ret == (char *)NULL)
  582.         return ((char *)NULL);
  583.     *flagp |= flags & (HASWIDTH | SPSTART);
  584.     break;
  585.     case '\0':
  586.     case OR_OP:
  587.     case RBRAC:
  588.     FAIL("internal urp");    /* Supposed to be caught earlier. */
  589.     break;
  590.     case ASTERIX:
  591.     FAIL("* follows nothing");
  592.     break;
  593.     default:{
  594.         register int    len;
  595.         register short  ender;
  596.  
  597.         regparse--;
  598.         for (len=0; regparse[len] &&
  599.             !(regparse[len]&SPECIAL) && regparse[len] != RSQBRAC; len++) ;
  600.         if (len <= 0)
  601.         {
  602.         FAIL("internal disaster");
  603.         }
  604.         ender = *(regparse + len);
  605.         if (len > 1 && ISMULT(ender))
  606.         len--;        /* Back off clear of * operand. */
  607.         *flagp |= HASWIDTH;
  608.         if (len == 1)
  609.         *flagp |= SIMPLE;
  610.         ret = regnode(EXACTLY);
  611.         while (len > 0) {
  612.         regc(*regparse++);
  613.         len--;
  614.         }
  615.         regc('\0');
  616.     }
  617.     break;
  618.     }
  619.  
  620.     return (ret);
  621. }
  622.  
  623. /*
  624.  - regnode - emit a node
  625.  */
  626. static char *regnode(op)
  627. char            op;
  628. {
  629.     register char  *ret;
  630.     register char  *ptr;
  631.  
  632.     ret = regcode;
  633.     if (ret == ®dummy) {
  634.     regsize += 3;
  635.     return (ret);
  636.     }
  637.     ptr = ret;
  638.     *ptr++ = op;
  639.     *ptr++ = '\0';        /* Null "nxt" pointer. */
  640.     *ptr++ = '\0';
  641.     regcode = ptr;
  642.  
  643.     return (ret);
  644. }
  645.  
  646. /*
  647.  - regc - emit (if appropriate) a byte of code
  648.  */
  649. static void regc(b)
  650. char            b;
  651. {
  652.     if (regcode != ®dummy)
  653.     *regcode++ = b;
  654.     else
  655.     regsize++;
  656. }
  657.  
  658. /*
  659.  - reginsert - insert an operator in front of already-emitted operand
  660.  *
  661.  * Means relocating the operand.
  662.  */
  663. static void reginsert(op, opnd)
  664. char            op;
  665. char           *opnd;
  666. {
  667.     register char  *src;
  668.     register char  *dst;
  669.     register char  *place;
  670.  
  671.     if (regcode == ®dummy) {
  672.     regsize += 3;
  673.     return;
  674.     }
  675.     src = regcode;
  676.     regcode += 3;
  677.     dst = regcode;
  678.     while (src > opnd)
  679.     *--dst = *--src;
  680.  
  681.     place = opnd;        /* Op node, where operand used to be. */
  682.     *place++ = op;
  683.     *place++ = '\0';
  684.     *place++ = '\0';
  685. }
  686.  
  687. /*
  688.  - regtail - set the next-pointer at the end of a node chain
  689.  */
  690. static void regtail(p, val)
  691. char           *p;
  692. char           *val;
  693. {
  694.     register char  *scan;
  695.     register char  *temp;
  696.     register int    offset;
  697.  
  698.     if (p == ®dummy)
  699.     return;
  700.  
  701.     /* Find last node. */
  702.     scan = p;
  703.     for (;;) {
  704.     temp = regnext(scan);
  705.     if (temp == (char *)NULL)
  706.         break;
  707.     scan = temp;
  708.     }
  709.  
  710.     if (OP(scan) == BACK)
  711.     offset = scan - val;
  712.     else
  713.     offset = val - scan;
  714.     *(scan + 1) = (offset >> 8) & 0377;
  715.     *(scan + 2) = offset & 0377;
  716. }
  717.  
  718. /*
  719.  - regoptail - regtail on operand of first argument; nop if operandless
  720.  */
  721. static void regoptail(p, val)
  722. char           *p;
  723. char           *val;
  724. {
  725.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  726.     if (p == (char *)NULL || p == ®dummy || OP(p) != BRANCH)
  727.     return;
  728.     regtail(OPERAND(p), val);
  729. }
  730.  
  731. /*
  732.  * regexec and friends
  733.  */
  734.  
  735. /*
  736.  * Global work variables for regexec().
  737.  */
  738. static char    *reginput;    /* String-input pointer. */
  739. static char    *regbol;        /* Beginning of input, for ^ check. */
  740. static char   **regstartp;    /* Pointer to startp array. */
  741. static char   **regendp;    /* Ditto for endp. */
  742.  
  743. /*
  744.  * Forwards.
  745.  */
  746. STATIC int      regtry();
  747. STATIC int      regmatch();
  748. STATIC int      regrepeat();
  749.  
  750. #ifdef DEBUG
  751. int             regnarrate = 0;
  752. void            regdump();
  753. STATIC char    *regprop();
  754. #endif
  755.  
  756. /*
  757.  - regexec - match a regexp against a string
  758.  */
  759. int regexec(prog, string)
  760. register regexp *prog;
  761. register char  *string;
  762. {
  763.     register char  *s;
  764.  
  765.     /* Be paranoid... */
  766.     if (prog == (regexp *)NULL || string == (char *)NULL) {
  767.     regerror("NULL parameter");
  768.     return (0);
  769.     }
  770.     /* Check validity of program. */
  771.     if (UCHARAT(prog->program) != MAGIC) {
  772.     regerror("corrupted program");
  773.     return (0);
  774.     }
  775.     /* If there is a "must appear" string, look for it. */
  776.     if (prog->regmust != (char *)NULL) {
  777.     s = string;
  778.     while ((s = strchr(s, prog->regmust[0])) != (char *)NULL) {
  779.         if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  780.         break;        /* Found it. */
  781.         s++;
  782.     }
  783.     if (s == (char *)NULL)        /* Not present. */
  784.         return (0);
  785.     }
  786.     /* Mark beginning of line for ^ . */
  787.     regbol = string;
  788.  
  789.     /* Simplest case:  anchored match need be tried only once. */
  790.     if (prog->reganch)
  791.     return (regtry(prog, string));
  792.  
  793.     /* Messy cases:  unanchored match. */
  794.     s = string;
  795.     if (prog->regstart != '\0')
  796.     /* We know what char it must start with. */
  797.     while ((s = strchr(s, prog->regstart)) != (char *)NULL) {
  798.         if (regtry(prog, s))
  799.         return (1);
  800.         s++;
  801.     }
  802.     else
  803.     /* We don't -- general case. */
  804.     do {
  805.         if (regtry(prog, s))
  806.         return (1);
  807.     } while (*s++ != '\0');
  808.  
  809.     /* Failure. */
  810.     return (0);
  811. }
  812.  
  813. /*
  814.  - regtry - try match at specific point
  815.  */
  816. #ifdef __STDC__
  817.  
  818. static int regtry(regexp *prog, char *string)
  819.  
  820. #else
  821.  
  822. static int regtry(prog, string)
  823. regexp         *prog;
  824. char           *string;
  825.  
  826. #endif
  827. {
  828.     register int    i;
  829.     register char **sp;
  830.     register char **ep;
  831.  
  832.     reginput = string;
  833.     regstartp = prog->startp;
  834.     regendp = prog->endp;
  835.  
  836.     sp = prog->startp;
  837.     ep = prog->endp;
  838.     for (i = NSUBEXP; i > 0; i--) {
  839.     *sp++ = (char *)NULL;
  840.     *ep++ = (char *)NULL;
  841.     }
  842.     if (regmatch(prog->program + 1)) {
  843.     prog->startp[0] = string;
  844.     prog->endp[0] = reginput;
  845.     return (1);
  846.     } else
  847.     return (0);
  848. }
  849.  
  850. /*
  851.  - regmatch - main matching routine
  852.  *
  853.  * Conceptually the strategy is simple:  check to see whether the current
  854.  * node matches, call self recursively to see whether the rest matches,
  855.  * and then act accordingly.  In practice we make some effort to avoid
  856.  * recursion, in particular by going through "ordinary" nodes (that don't
  857.  * need to know whether the rest of the match failed) by a loop instead of
  858.  * by recursion.
  859.  */
  860. #ifdef __STDC__
  861.  
  862. static int regmatch(char *prog)
  863.  
  864. #else
  865.  
  866. static int regmatch(prog)
  867. char           *prog;
  868.  
  869. #endif
  870. {
  871.     register char  *scan;    /* Current node. */
  872.     char           *nxt;    /* nxt node. */
  873.  
  874.     scan = prog;
  875. #ifdef DEBUG
  876.     if (scan != (char *)NULL && regnarrate)
  877.     fprintf(stderr, "%s(\n", regprop(scan));
  878. #endif
  879.     while (scan != (char *)NULL) {
  880. #ifdef DEBUG
  881.     if (regnarrate)
  882.         fprintf(stderr, "%s...\n", regprop(scan));
  883. #endif
  884.     nxt = regnext(scan);
  885.  
  886.     switch (OP(scan)) {
  887.     case BOL:
  888.         if (reginput != regbol)
  889.         return (0);
  890.         break;
  891.     case EOL:
  892.         if (*reginput != '\0')
  893.         return (0);
  894.         break;
  895.     case ANY:
  896.         if (*reginput == '\0')
  897.         return (0);
  898.         reginput++;
  899.         break;
  900.     case WORDSTART:
  901.         if (reginput == regbol)
  902.         break;
  903.         if (*reginput == '\0' ||
  904.            ISWORDPART( *(reginput-1) ) || !ISWORDPART( *reginput ) )
  905.         return (0);
  906.         break;
  907.     case WORDEND:
  908.         if (*reginput == '\0')
  909.         break;
  910.         if ( reginput == regbol ||
  911.            !ISWORDPART( *(reginput-1) ) || ISWORDPART( *reginput ) )
  912.         return (0);
  913.         break;
  914.     case EXACTLY:{
  915.         register int    len;
  916.         register char  *opnd;
  917.  
  918.         opnd = OPERAND(scan);
  919.         /* Inline the first character, for speed. */
  920.         if (*opnd != *reginput)
  921.             return (0);
  922.         len = strlen(opnd);
  923.         if (len > 1 && strncmp(opnd, reginput, len) != 0)
  924.             return (0);
  925.         reginput += len;
  926.         }
  927.         break;
  928.     case ANYOF:
  929.         if (*reginput == '\0' || 
  930.          strchr(OPERAND(scan), *reginput) == (char *)NULL)
  931.         return (0);
  932.         reginput++;
  933.         break;
  934.     case ANYBUT:
  935.         if (*reginput == '\0' || 
  936.          strchr(OPERAND(scan), *reginput) != (char *)NULL)
  937.         return (0);
  938.         reginput++;
  939.         break;
  940.     case NOTHING:
  941.         break;
  942.     case BACK:
  943.         break;
  944.     case OPEN + 1:
  945.     case OPEN + 2:
  946.     case OPEN + 3:
  947.     case OPEN + 4:
  948.     case OPEN + 5:
  949.     case OPEN + 6:
  950.     case OPEN + 7:
  951.     case OPEN + 8:
  952.     case OPEN + 9:{
  953.         register int    no;
  954.         register char  *save;
  955.  
  956.         no = OP(scan) - OPEN;
  957.         save = reginput;
  958.  
  959.         if (regmatch(nxt)) {
  960.             /*
  961.              * Don't set startp if some later invocation of the same
  962.              * parentheses already has. 
  963.              */
  964.             if (regstartp[no] == (char *)NULL)
  965.             regstartp[no] = save;
  966.             return (1);
  967.         } else
  968.             return (0);
  969.         }
  970.         break;
  971.     case CLOSE + 1:
  972.     case CLOSE + 2:
  973.     case CLOSE + 3:
  974.     case CLOSE + 4:
  975.     case CLOSE + 5:
  976.     case CLOSE + 6:
  977.     case CLOSE + 7:
  978.     case CLOSE + 8:
  979.     case CLOSE + 9:{
  980.         register int    no;
  981.         register char  *save;
  982.  
  983.         no = OP(scan) - CLOSE;
  984.         save = reginput;
  985.  
  986.         if (regmatch(nxt)) {
  987.             /*
  988.              * Don't set endp if some later invocation of the same
  989.              * parentheses already has. 
  990.              */
  991.             if (regendp[no] == (char *)NULL)
  992.             regendp[no] = save;
  993.             return (1);
  994.         } else
  995.             return (0);
  996.         }
  997.         break;
  998.     case BRANCH:{
  999.         register char  *save;
  1000.  
  1001.         if (OP(nxt) != BRANCH)    /* No choice. */
  1002.             nxt = OPERAND(scan);    /* Avoid recursion. */
  1003.         else {
  1004.             do {
  1005.             save = reginput;
  1006.             if (regmatch(OPERAND(scan)))
  1007.                 return (1);
  1008.             reginput = save;
  1009.             scan = regnext(scan);
  1010.             } while (scan != (char *)NULL && OP(scan) == BRANCH);
  1011.             return (0);
  1012.             /* NOTREACHED */
  1013.         }
  1014.         }
  1015.         break;
  1016.     case STAR:{
  1017.         register char   nextch;
  1018.         register int    no;
  1019.         register char  *save;
  1020.         register int    minimum;
  1021.  
  1022.         /*
  1023.          * Lookahead to avoid useless match attempts when we know
  1024.          * what character comes next. 
  1025.          */
  1026.         nextch = '\0';
  1027.         if (OP(nxt) == EXACTLY)
  1028.             nextch = *OPERAND(nxt);
  1029.         minimum = (OP(scan) == STAR) ? 0 : 1;
  1030.         save = reginput;
  1031.         no = regrepeat(OPERAND(scan));
  1032.         while (no >= minimum) {
  1033.             /* If it could work, try it. */
  1034.             if (nextch == '\0' || *reginput == nextch)
  1035.             if (regmatch(nxt))
  1036.                 return (1);
  1037.             /* Couldn't or didn't -- back up. */
  1038.             no--;
  1039.             reginput = save + no;
  1040.         }
  1041.         return (0);
  1042.         }
  1043.         break;
  1044.     case END:
  1045.         return (1);        /* Success! */
  1046.         break;
  1047.     default:
  1048.         regerror("memory corruption");
  1049.         return (0);
  1050.         break;
  1051.     }
  1052.  
  1053.     scan = nxt;
  1054.     }
  1055.  
  1056.     /*
  1057.      * We get here only if there's trouble -- normally "case END" is the
  1058.      * terminating point. 
  1059.      */
  1060.     regerror("corrupted pointers");
  1061.     return (0);
  1062. }
  1063.  
  1064. /*
  1065.  - regrepeat - repeatedly match something simple, report how many
  1066.  */
  1067. #ifdef __STDC__
  1068.  
  1069. static int regrepeat(char *p)
  1070.  
  1071. #else
  1072.  
  1073. static int regrepeat(p)
  1074. char           *p;
  1075.  
  1076. #endif
  1077. {
  1078.     register int    count = 0;
  1079.     register char  *scan;
  1080.     register char  *opnd;
  1081.  
  1082.     scan = reginput;
  1083.     opnd = OPERAND(p);
  1084.     switch (OP(p)) {
  1085.     case ANY:
  1086.     count = strlen(scan);
  1087.     scan += count;
  1088.     break;
  1089.     case EXACTLY:
  1090.     while (*opnd == *scan) {
  1091.         count++;
  1092.         scan++;
  1093.     }
  1094.     break;
  1095.     case ANYOF:
  1096.     while (*scan != '\0' && strchr(opnd, *scan) != (char *)NULL) {
  1097.         count++;
  1098.         scan++;
  1099.     }
  1100.     break;
  1101.     case ANYBUT:
  1102.     while (*scan != '\0' && strchr(opnd, *scan) == (char *)NULL) {
  1103.         count++;
  1104.         scan++;
  1105.     }
  1106.     break;
  1107.     default:            /* Oh dear.  Called inappropriately. */
  1108.     regerror("internal foulup");
  1109.     count = 0;        /* Best compromise. */
  1110.     break;
  1111.     }
  1112.     reginput = scan;
  1113.  
  1114.     return (count);
  1115. }
  1116.  
  1117.  
  1118. /*
  1119.  - regnext - dig the "nxt" pointer out of a node
  1120.  */
  1121. #ifdef __STDC__
  1122.  
  1123. static char *regnext(register char *p)
  1124.  
  1125. #else
  1126.  
  1127. static char *regnext(p)
  1128. register char  *p;
  1129.  
  1130. #endif
  1131. {
  1132.     register int    offset;
  1133.  
  1134.     if (p == ®dummy)
  1135.     return ((char *)NULL);
  1136.  
  1137.     offset = NEXT(p);
  1138.     if (offset == 0)
  1139.     return ((char *)NULL);
  1140.  
  1141.     if (OP(p) == BACK)
  1142.     return (p - offset);
  1143.     else
  1144.     return (p + offset);
  1145. }
  1146.  
  1147. #ifdef DEBUG
  1148.  
  1149. STATIC char    *regprop();
  1150.  
  1151. /*
  1152.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1153.  */
  1154. #ifdef __STDC__
  1155.  
  1156. void regdump(regexp *r)
  1157.  
  1158. #else
  1159.  
  1160. void regdump(r)
  1161. regexp         *r;
  1162.  
  1163. #endif
  1164. {
  1165.     register char  *s;
  1166.     register char   op = EXACTLY;    /* Arbitrary non-END op. */
  1167.     register char  *nxt;
  1168.     extern char    *strchr();
  1169.  
  1170.  
  1171.     s = r->program + 1;
  1172.     while (op != END) {        /* While that wasn't END last time... */
  1173.     op = OP(s);
  1174.     printf("%2d%s", s - r->program, regprop(s));    /* Where, what. */
  1175.     nxt = regnext(s);
  1176.     if (nxt == (char *)NULL)    /* nxt ptr. */
  1177.         printf("(0)");
  1178.     else
  1179.         printf("(%d)", (s - r->program) + (nxt - s));
  1180.     s += 3;
  1181.     if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1182.         /* Literal string, where present. */
  1183.         while (*s != '\0') {
  1184.         putchar(*s);
  1185.         s++;
  1186.         }
  1187.         s++;
  1188.     }
  1189.     putchar('\n');
  1190.     }
  1191.  
  1192.     /* Header fields of interest. */
  1193.     if (r->regstart != '\0')
  1194.     printf("start `%c' ", r->regstart);
  1195.     if (r->reganch)
  1196.     printf("anchored ");
  1197.     if (r->regmust != (char *)NULL)
  1198.     printf("must have \"%s\"", r->regmust);
  1199.     printf("\n");
  1200. }
  1201.  
  1202. /*
  1203.  - regprop - printable representation of opcode
  1204.  */
  1205. #ifdef __STDC__
  1206.  
  1207. static char *regprop(char *op)
  1208.  
  1209. #else
  1210.  
  1211. static char *regprop(op)
  1212. char           *op;
  1213.  
  1214. #endif
  1215. {
  1216.     register char  *p;
  1217.     static char     buf[50];
  1218.  
  1219.     strcpy(buf, ":");
  1220.  
  1221.     switch (OP(op)) {
  1222.     case BOL:
  1223.     p = "BOL";
  1224.     break;
  1225.     case EOL:
  1226.     p = "EOL";
  1227.     break;
  1228.     case ANY:
  1229.     p = "ANY";
  1230.     break;
  1231.     case ANYOF:
  1232.     p = "ANYOF";
  1233.     break;
  1234.     case ANYBUT:
  1235.     p = "ANYBUT";
  1236.     break;
  1237.     case BRANCH:
  1238.     p = "BRANCH";
  1239.     break;
  1240.     case EXACTLY:
  1241.     p = "EXACTLY";
  1242.     break;
  1243.     case NOTHING:
  1244.     p = "NOTHING";
  1245.     break;
  1246.     case BACK:
  1247.     p = "BACK";
  1248.     break;
  1249.     case END:
  1250.     p = "END";
  1251.     break;
  1252.     case OPEN + 1:
  1253.     case OPEN + 2:
  1254.     case OPEN + 3:
  1255.     case OPEN + 4:
  1256.     case OPEN + 5:
  1257.     case OPEN + 6:
  1258.     case OPEN + 7:
  1259.     case OPEN + 8:
  1260.     case OPEN + 9:
  1261.     sprintf(buf + strlen(buf), "OPEN%d", OP(op) - OPEN);
  1262.     p = (char *)NULL;
  1263.     break;
  1264.     case CLOSE + 1:
  1265.     case CLOSE + 2:
  1266.     case CLOSE + 3:
  1267.     case CLOSE + 4:
  1268.     case CLOSE + 5:
  1269.     case CLOSE + 6:
  1270.     case CLOSE + 7:
  1271.     case CLOSE + 8:
  1272.     case CLOSE + 9:
  1273.     sprintf(buf + strlen(buf), "CLOSE%d", OP(op) - CLOSE);
  1274.     p = (char *)NULL;
  1275.     break;
  1276.     case STAR:
  1277.     p = "STAR";
  1278.     break;
  1279.     default:
  1280.     regerror("corrupted opcode");
  1281.     break;
  1282.     }
  1283.     if (p != (char *)NULL)
  1284.     strcat(buf, p);
  1285.     return (buf);
  1286. }
  1287. #endif
  1288.  
  1289. /*
  1290.  * The following is provided for those people who do not have strcspn() in
  1291.  * their C libraries.  They should get off their butts and do something
  1292.  * about it; at least one public-domain implementation of those (highly
  1293.  * useful) string routines has been published on Usenet.
  1294.  */
  1295. #ifdef STRCSPN
  1296. /*
  1297.  * strcspn - find length of initial segment of s1 consisting entirely
  1298.  * of characters not from s2
  1299.  */
  1300.  
  1301. #ifdef __STDC__
  1302.  
  1303. static int strcspn(char *s1, char *s2)
  1304.  
  1305. #else
  1306.  
  1307. static int strcspn(s1, s2)
  1308. char           *s1;
  1309. char           *s2;
  1310.  
  1311. #endif
  1312. {
  1313.     register char  *scan1;
  1314.     register char  *scan2;
  1315.     register int    count;
  1316.  
  1317.     count = 0;
  1318.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1319.     for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1320.         if (*scan1 == *scan2++)
  1321.         return (count);
  1322.     count++;
  1323.     }
  1324.     return (count);
  1325. }
  1326. #endif
  1327.  
  1328.  
  1329. /*
  1330.  - regsub - perform substitutions after a regexp match
  1331.  */
  1332. #ifdef __STDC__
  1333.  
  1334. char *regsub(regexp *prog, char *source, char *dest, int n)
  1335.  
  1336. #else
  1337.  
  1338. char *regsub(prog, source, dest, n)
  1339. regexp         *prog;
  1340. char           *source;
  1341. char           *dest;
  1342. int        n;
  1343.  
  1344. #endif
  1345. {
  1346.     register char  *src;
  1347.     register char  *dst;
  1348.     register char   c;
  1349.     register int    no;
  1350.     register int    len;
  1351.     extern char    *strncpy();
  1352.  
  1353.     if (prog == (regexp *)NULL || 
  1354.     source == (char *)NULL || dest == (char *)NULL) {
  1355.     regerror("NULL parm to regsub");
  1356.     return NULL;
  1357.     }
  1358.     if (UCHARAT(prog->program) != MAGIC) {
  1359.     regerror("damaged regexp fed to regsub");
  1360.     return NULL;
  1361.     }
  1362.     src = source;
  1363.     dst = dest;
  1364.     while ((c = *src++) != '\0') {
  1365.     if (c == '&')
  1366.         no = 0;
  1367.     else if (c == '\\' && '0' <= *src && *src <= '9')
  1368.         no = *src++ - '0';
  1369.     else
  1370.         no = -1;
  1371.  
  1372.     if (no < 0) {        /* Ordinary character. */
  1373.         if (c == '\\' && (*src == '\\' || *src == '&'))
  1374.         c = *src++;
  1375.         if (--n < 0) {                /* amylaar */
  1376.         regerror("line too long");
  1377.         return NULL;
  1378.         }
  1379.         *dst++ = c;
  1380.     } else if (prog->startp[no] != (char *)NULL && 
  1381.            prog->endp[no] != (char *)NULL) {
  1382.         len = prog->endp[no] - prog->startp[no];
  1383.         if ( (n-=len) < 0 ) {        /* amylaar */
  1384.         regerror("line too long");
  1385.         return NULL;
  1386.         }
  1387.         strncpy(dst, prog->startp[no], len);
  1388.         dst += len;
  1389.         if (len != 0 && *(dst - 1) == '\0') {    /* strncpy hit NUL. */
  1390.         regerror("damaged match string");
  1391.         return NULL;
  1392.         }
  1393.     }
  1394.     }
  1395.     if (--n < 0) {            /* amylaar */
  1396.         regerror("line too long");
  1397.         return NULL;
  1398.     }
  1399.     *dst = '\0';
  1400.     return dst;
  1401. }
  1402.  
  1403.  
  1404. #if 0    /* Use the local regerror() in ed.c */
  1405. #ifdef __STDC__
  1406.  
  1407. void regerror(char *s)
  1408.  
  1409. #else
  1410.  
  1411. void regerror(s)
  1412. char           *s;
  1413.  
  1414. #endif
  1415. {
  1416.     fprintf(stderr, "regexp(3): %s", s);
  1417.     exit(1);
  1418. }
  1419. #endif /* 0 */
  1420.